1. Field of Invention
The present invention pertains to the field of random number generators. More particularly, this invention relates to a verifiable random number generator using chaos.
2. Art Background
Random number generators may be employed in a variety of applications. For example, random number generators may be used in cryptography to generate cryptographic keys. Other example applications of random number generators include test data generation, Monte-Carlo simulation, and spread-spectrum communication to name a few.
A random number generator may be based on a chaotic system in which random numbers are derived from the states of the chaotic system. A chaotic system may be defined as one in which two particles in nearly identically states separate exponentially fast with time. It is usually desirable that the exponential separation be great enough to prevent the prediction of the state of the two particles at some time sufficiently far in the future based on the current state of the two particles.
A chaotic system suitable for use in a random number generator may be implemented using an oscillator circuit in which the two separating particles are represented by electrical properties of the oscillator circuit such as voltage or current states. Typically, the exponential separation in these oscillator states is determined by the oscillator frequency times a constant which is commonly referred to as the Lyupanov exponent. Typically, the oscillator circuit is implemented so that the Lyupanov exponent is high enough to provide sufficient separation in the oscillator states over time to yield chaotic behavior.
Hardware failures in an oscillator circuit and/or unforseen system interactions between an oscillator circuit and other elements of a system may cause the effective value of the Lyupanov exponent to approach an undesirably low value. Unfortunately, a low value of the Lyupanov exponent may increase the predictability of the oscillator states, thereby increasing the predictability of random numbers derived from the oscillator states. In a cryptographic system, for example, predictable oscillator states may enable the determination of cryptographic keys which are based on random numbers derived from the oscillator states, thereby enabling unauthorized parties to crack the cryptographic system.
A verifiable random number generator is disclosed that includes mechanisms for monitoring its chaotic behavior. A random number generator according to the present teachings includes a chaos circuit that generates a number according to a chaos function. The random number generator further includes a check circuit that simulates the chaos function and that determines whether the number is a valid random number by monitoring the chaotic behavior of the chaos function as indicated by the Lyupanov exponent.
Other features and advantages of the present invention will be apparent from the detailed description that follows.